import unittest

from lib import *
from main import *

class TestTree(unittest.TestCase):
    def test_evaluate_tree(self):
        '''
        Test evaluate binary tree
        '''
        parser = EvaluateByTree()
        expression = "((3.3*(23-(((100%7)!)*10.5)))/3)"
        answer = (3.3*(23-(EvaluateByTree.factorial(100%7,1))*10.5))/3
        result = parser.evaluate(expression)
        self.assertEqual(answer, result)

    def test_SortByBinaryHeap(self):
        '''
        Test sort by binary heap
        '''
        Heap = BinHeap()
        N = 100000
        inlst = list()
        for key in IntGenerator(N):
            Heap.insert(key)
            inlst.append(key)
        temp = list()
        for _ in range(N):
            temp.append(Heap.pop())
        self.assertTrue(temp == sorted(inlst)) # Insert Sorting
        self.assertTrue(SortByBinaryHeap(inlst) == sorted(inlst)) # Build Sorting


class TestBST(unittest.TestCase):
    def test_BST_inorder(self):
        '''
        Teat mid-order traversal in binary search tree
        '''
        bst = BSTadvance()
        N = 1000
        inlst = list()
        for key in IntGenerator(N):
            bst.put(key,str(key))
            inlst.append(key)
        bst.delete(inlst[23])
        inlst.pop(23)
        self.assertEqual(bst.inorder(),sorted(inlst))

    def test_BST_same_key(self):
        '''
        Test key-value update
        '''
        """ old BAT will keep same key in tree """
        bst = BinarySearchTree()
        bst[114] = "114"
        bst[114] = "514"
        self.assertEqual(bst[114],"114") #  expect to 514
        del bst[114]
        self.assertEqual(bst[114],"514") #  expect to None

        """ delete key to test new BAT update """
        bst = BSTadvance()
        N = 1000
        for key in IntGenerator(N):
            bst.put(key,str(key))
        bst[114] = "114"
        bst[114] = "514"
        self.assertEqual(bst[114],"514")
        del bst[114]
        self.assertEqual(bst[114],None)

    def test_ThreadedBST(self):
        '''
        Test threaded binary search tree
        '''
        bst = ThreadedBST()
        N = 1000
        inlst = list()
        for key in IntGenerator(N):
            bst.put(key,str(key))
            inlst.append(key)
        self.assertEqual(bst.inorder(),sorted(inlst))
        self.assertEqual(bst.inorder(reverse=True),sorted(inlst,reverse=True))


class TestAVLtree(unittest.TestCase):
    def setUp(self):
        self.AVLtree = AVLadvance()
        for key in range(1,10):
            self.AVLtree[key] = str(key)
        """ expect
              4
          2       6
        1   3   5   8
                   7 9
        """
        self.assertEqual(self.AVLtree.root.key,4)
        self.assertEqual(self.AVLtree.root.balanceFactor,-1)
        self.assertEqual(self.AVLtree.root.leftChild.rightChild.key,3)
        self.assertEqual(self.AVLtree.root.rightChild.rightChild.leftChild.key,7)
        self.assertEqual(self.AVLtree.root.rightChild.balanceFactor,-1)

    def test_delete_leaf(self):
        '''
        Test AVL tree delete leaf node
        '''

        """ need to rebalance parent """
        del self.AVLtree[5]
        """ expect
              4
          2       8
        1   3   6   9
                 7
        """
        self.assertEqual(self.AVLtree.root.rightChild.leftChild.rightChild.key,7)
        self.assertEqual(self.AVLtree.root.rightChild.rightChild.key,9)
        self.assertEqual(self.AVLtree.root.balanceFactor,-1)
        self.assertEqual(self.AVLtree.root.leftChild.balanceFactor,0)
        self.assertEqual(self.AVLtree.root.rightChild.balanceFactor,1)

        """ should not change the balanceFactor of grandparent """
        del self.AVLtree[3]
        """ expect
              4
          2       8
        1       6   9
                 7
        """
        self.assertEqual(self.AVLtree.root.leftChild.balanceFactor,1)
        self.assertEqual(self.AVLtree.root.balanceFactor,-1)

        """ should change the balanceFactor of grandparent """
        del self.AVLtree[7]
        """ expect
              4
          2       8
        1       6   9
        """
        self.assertEqual(self.AVLtree.root.rightChild.leftChild.balanceFactor,0)
        self.assertEqual(self.AVLtree.root.rightChild.balanceFactor,0)
        self.assertEqual(self.AVLtree.root.balanceFactor,0)  

    def test_delete_one_child(self):
        '''
        Test AVL tree delete node only have one child
        '''

        del self.AVLtree[7]
        del self.AVLtree[8]

        """ should not rebalance but should change balanceFactor"""
        """ expect
              4
          2       6
        1   3   5   9
        """
        self.assertEqual(self.AVLtree.root.balanceFactor,0)
        self.assertEqual(self.AVLtree.root.rightChild.leftChild.key,5)
        self.assertEqual(self.AVLtree.root.rightChild.balanceFactor,0)
        self.assertEqual(self.AVLtree.root.rightChild.rightChild.key,9)

        """ should rebalance """
        self.AVLtree[8] = str(8)
        del self.AVLtree[3]
        self.assertEqual(self.AVLtree.root.balanceFactor,-1)
        del self.AVLtree[2]
        """ expect
              6
          4       9
        1   5   8 
        """
        self.assertEqual(self.AVLtree.root.balanceFactor,0)
        self.assertEqual(self.AVLtree.root.key,6)
        self.assertEqual(self.AVLtree.root.leftChild.key,4)
        self.assertEqual(self.AVLtree.root.leftChild.rightChild.key,5)
        self.assertEqual(self.AVLtree.root.rightChild.key,9)

    def test_delete_both_child(self):
        '''
        Test AVL tree delete node have both child
        '''
        """ the successor is leaf """
        del self.AVLtree[4]
        """ expect
              5
          2       8
        1   3   6   9
                 7
        """
        self.assertEqual(self.AVLtree.root.key,5)
        self.assertEqual(self.AVLtree.root.rightChild.leftChild.rightChild.key,7)
        self.assertEqual(self.AVLtree.root.rightChild.rightChild.key,9)
        self.assertEqual(self.AVLtree.root.balanceFactor,-1)
        self.assertEqual(self.AVLtree.root.leftChild.balanceFactor,0)
        self.assertEqual(self.AVLtree.root.rightChild.balanceFactor,1)

        """ the successor is not leaf """
        self.AVLtree[10] = str(10)
        del self.AVLtree[5]
        """ expect
              6
          2       8
        1   3   7   9
                     10
        """
        self.assertEqual(self.AVLtree.root.key,6)
        self.assertEqual(self.AVLtree.root.rightChild.leftChild.key,7)
        self.assertEqual(self.AVLtree.root.rightChild.balanceFactor,-1)
        self.assertEqual(self.AVLtree.root.balanceFactor,-1)

    def test_random_put_delete(self):
        '''
        Test AVL tree random put and delete 
        '''
        self.AVLtree = AVLadvance()
        inlst = list()
        """ random put in """
        for key in IntGenerator(1000):
            self.AVLtree[key] = str(key)
            inlst.append(key)
        """ random delete out """
        for index in range(0,1000,2):
            del self.AVLtree[inlst[index]]
            inlst[index] = None
        
        for key in inlst:
            if isinstance(key,int):
                self.assertEqual(self.AVLtree[key],str(key))

if __name__ == "__main__":
    unittest.main()